export class UnionFind1 {
    constructor(size) {
        this.id = new Array(size)

        for (let i = 0; i < size; i++) {
            this.id[i] = i
        }
    }

    getSize() {
        return this.id.length
    }

    find(p) {
        if (p < 0 || p >= this.getSize()) {
            throw new Error('p is out of bound.')
        }
        return this.id[p]
    }

    isConnected(p, q) {
        return this.find(p) === this.find(q)
    }

    unionElement(p, q) {
        const pId = this.find(p)
        const qId = this.find(q)

        if (pId === qId) {
            return
        }

        for (let i = 0; i < this.id.length; i++) {
            if (this.id[i] === pId) {
                this.id[i] = qId
            }
        }
    }
}


export class UnionFind2 {
    constructor(size) {
        this.parent = new Array(size)

        for (let i = 0; i < size; i++) {
            this.parent[i] = i
        }
    }

    getSize() {
        return this.parent.length
    }

    find(p) {
        if (p < 0 || p >= this.getSize()) {
            throw new Error('p is out of bound.')
        }

        while (p !== this.parent[p]) {
            p = this.parent[p]
        }

        return p
    }

    isConnected(p, q) {
        return this.find(p) === this.find(q)
    }

    unionElement(p, q) {
        let pRoot = this.find(p)
        let qRoot = this.find(q)

        if (pRoot === qRoot) {
            return
        }

        this.parent[pRoot] = qRoot
    }
}


export class UnionFind3 {
    constructor(size) {
        this.parent = new Array(size)
        this.sz = new Array(size) // sz[i] 表示以 i 为根的集合中元素的个数

        for (let i = 0; i < size; i++) {
            this.parent[i] = i
            this.sz[i] = 1
        }
    }

    getSize() {
        return this.parent.length
    }

    find(p) {
        if (p < 0 || p >= this.getSize()) {
            throw new Error('p is out of bound.')
        }

        while (p !== this.parent[p]) {
            p = this.parent[p]
        }

        return p
    }

    isConnected(p, q) {
        return this.find(p) === this.find(q)
    }

    unionElement(p, q) {
        let pRoot = this.find(p)
        let qRoot = this.find(q)

        if (pRoot === qRoot) {
            return
        }

        if (this.sz[pRoot] < this.sz[qRoot]) {
            this.parent[pRoot] = qRoot
            this.sz[qRoot] += this.sz[pRoot]

        } else {
            this.parent[qRoot] = pRoot
            this.sz[pRoot] += this.sz[qRoot]

        }
    }

}


export class UnionFind4 {
    constructor(size) {
        this.parent = new Array(size)
        this.rank = new Array(size)

        for (let i = 0; i < size; i++) {
            this.parent[i] = i
            this.rank[i] = 1
        }
    }

    getSize() {
        return this.parent.length
    }

    find(p) {
        if (p < 0 || p >= this.getSize()) {
            throw new Error('p is out of bound.')
        }

        while (p !== this.parent[p]) {
            p = this.parent[p]
        }

        return p
    }

    isConnected(p, q) {
        return this.find(p) === this.find(q)
    }

    unionElement(p, q) {
        let pRoot = this.find(p)
        let qRoot = this.find(q)

        if (pRoot === qRoot) {
            return
        }

        if (this.rank[pRoot] < this.rank[qRoot]) {
            this.parent[pRoot] = qRoot

        } else if (this.rank[pRoot] > this.rank[qRoot]) {
            this.parent[qRoot] = pRoot

        } else {
            this.parent[qRoot] = pRoot
            this.rank[pRoot]++

        }
    }

}


export class UnionFind5 {
    constructor(size) {
        this.parent = new Array(size)
        this.rank = new Array(size)

        for (let i = 0; i < size; i++) {
            this.parent[i] = i
            this.rank[i] = 1
        }
    }

    getSize() {
        return this.parent.length
    }

    find(p) {
        if (p < 0 || p >= this.getSize()) {
            throw new Error('p is out of bound.')
        }

        while (p !== this.parent[p]) {
            this.parent[p] = this.parent[this.parent[p]]
            p = this.parent[p]
        }

        return p
    }

    isConnected(p, q) {
        return this.find(p) === this.find(q)
    }

    unionElement(p, q) {
        let pRoot = this.find(p)
        let qRoot = this.find(q)

        if (pRoot === qRoot) {
            return
        }

        if (this.rank[pRoot] < this.rank[qRoot]) {
            this.parent[pRoot] = qRoot

        } else if (this.rank[pRoot] > this.rank[qRoot]) {
            this.parent[qRoot] = pRoot

        } else {
            this.parent[qRoot] = pRoot
            this.rank[pRoot]++

        }
    }

}


export class UnionFind6 {
    constructor(size) {
        this.parent = new Array(size)
        this.rank = new Array(size)

        for (let i = 0; i < size; i++) {
            this.parent[i] = i
            this.rank[i] = 1
        }
    }

    getSize() {
        return this.parent.length
    }

    find(p) {
        if (p < 0 || p >= this.getSize()) {
            throw new Error('p is out of bound.')
        }

        if (p !== this.parent[p]) {
            this.parent[p] = this.find(this.parent[p])
        }

        return this.parent[p]
    }

    isConnected(p, q) {
        return this.find(p) === this.find(q)
    }

    unionElement(p, q) {
        let pRoot = this.find(p)
        let qRoot = this.find(q)

        if (pRoot === qRoot) {
            return
        }

        if (this.rank[pRoot] < this.rank[qRoot]) {
            this.parent[pRoot] = qRoot

        } else if (this.rank[pRoot] > this.rank[qRoot]) {
            this.parent[qRoot] = pRoot

        } else {
            this.parent[qRoot] = pRoot
            this.rank[pRoot]++

        }
    }

}